#include "paint.h"

#include <vector>
#include <set>
#include <cstring>
#include <iostream>

using namespace std;

#define vec vector<int>

const int MN = 1e5+10;

set<int> lov[MN];

int n,m,k,c[MN];
int f[2][MN],g[MN];

int minimumInstructions(
    int N, int M, int K, std::vector<int> C,std::vector<int> A, std::vector<std::vector<int>> B){
	n = N,m = M; k = K;
	for(int i = 0;i < m;i++) for(int x : B[i]) lov[x].insert(i);
	for(int i = 1;i <= n;i++) c[i] = C[i-1];
	int o = 1; memset(f,0,sizeof f);
	for(int i = n;i >= 1;i--,o ^= 1){
		if(i + 2 <= n) for(int x : lov[c[i + 2]]) f[o][x] = 0;
		int mx = 0;
		for(int x : lov[c[i]]) f[o][x] = max(f[o][x],f[o ^ 1][(x + 1) % m] + 1),mx = max(f[o][x],mx);
		if(mx >= m) g[i] = m; else g[i] = -1;
	}
	int l = 1,r = 1,ans = 0;
	while(r <= n){
		int mx = -1;
		while(l <= r) mx = ~g[l] && g[l] + l - 1 >= r ? max(mx,g[l] + l - 1) : mx,l++;
		if(mx == -1) return -1;
		r = mx + 1; ans++;
	}
	return ans;
}
